package 集合;

public class LinkedList<E> {
	private int size;
	private Node<E> first;
	
	protected static final int ELEMENT_NOT_FOUND = -1;
	private static class Node<E> {
//		E element;
//		Node<E> next;
//		public Node(E element, Node<E> next) {
//			this.element = element;
//			this.next = next;
//		}
		
		E element;
		Node<E> next;
		public Node(E element, Node<E> next) {
			this.element = element;
			this.next = next;
		}
	}
	
	public int size() {
		return size;
	}
	
	public boolean isEmpty() {
		return size == 0;
	}
	
	public void clear() {
		size = 0;
		first = null;
	}
	
	public int indexOf(E element) {
		for (int i = 0; i < size; i++) {
			if(element == node(i).element)
				return i;
		}
		
		return ELEMENT_NOT_FOUND;
	}
	public boolean contains(E element) {
		return indexOf(element) != ELEMENT_NOT_FOUND;
	}
	
	public E get(int index) {
		return node(index).element;
	}
	
	public void add(E element) {
		add(size, element);
	}
	
	public void add(int index, E element) {
		if(index == 0) {
			Node<E> node = new Node<>(element, null);
			first = node;
		} else {
			Node<E> prev = node(index - 1);
			Node<E> node = new Node<>(element, prev.next);
			prev.next = node;			
		}
		
		size++;
	}
	
	public Node<E> node(int index) {
		Node<E> node = first;
		if(index != 0) {		
			for (int i = 0; i < size; i++) {
				if(i == index)
					return node;
				node = node.next;
			}
		}	
		return node;
	}
	
	@Override
	public String toString() {
		StringBuilder string = new StringBuilder();
		string.append("size=").append(size).append(", [");
		Node<E> node = first;
		for (int i = 0; i < size; i++) {
			if (i != 0) {
				string.append(", ");
			}
			
			string.append(node.element);
			
			node = node.next;
		}
		string.append("]");
		return string.toString();
	}
}
